package com.example.leetcode.c1_c100.c60;
/**
 * 给出集合 [1,2,3,…,n]，其所有元素共有 n! 种排列。
 *
 * 按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：
 *
 * "123"
 * "132"
 * "213"
 * "231"
 * "312"
 * "321"
 * 给定 n 和 k，返回第 k 个排列。
 *
 * 说明：
 *
 * 给定 n 的范围是 [1, 9]。
 * 给定 k 的范围是[1,  n!]。
 * 示例 1:
 *
 * 输入: n = 3, k = 3
 * 输出: "213"
 * 示例 2:
 *
 * 输入: n = 4, k = 9
 * 输出: "2314"
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/permutation-sequence
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

import java.util.LinkedList;
import java.util.List;

/**
 * 第k个排列
 * @author zhanpengguo
 * @date 2020-09-15 13:02
 */
public class Solution {



    public String getPermutation(int n, int k) {
        StringBuffer sb = new StringBuffer();
        // 未使用的有序元素
        List<Integer> list = new LinkedList<>();
        for (int i = 1; i <= n; i++) {
            list.add(i);
        }
        // 每个元素对应的阶乘
        int[] jies = new int[n];
        jies[0] = 1;
        for (int i = 1; i < n; i++) {
            jies[i] = jies[i - 1] * i;
        }
        k--;
        for (int i = n - 1; i >= 0; i--) {
            int index = k / jies[i] ;
            sb.append(list.remove(index));
            k -= index * jies[i];
        }
        return sb.toString();
    }


    public static void main(String[] args) {
        Solution solution = new Solution();
        String permutation = solution.getPermutation(3, 2);
        System.out.println(permutation);
    }
}
